//
// Created by cljh on 2023/3/28.
//

#ifndef BIN_PACKING_GEOMETRYUTILS_H
#define BIN_PACKING_GEOMETRYUTILS_H

#include <iostream>
#include <set>
#include "../entity/Point.h"
#include "../entity/Segment.h"
#include "../entity/Polygon.h"
#include "../entity/NestPath.h"


#define equals(a,b) (fabs((a)-(b))<EPS)
class GeometryUtils{
public:
    static double dot(Vector a,Vector b){
        return a.x*b.x+a.y*b.y;
    }
    static double cross(Vector a,Vector b){
        return a.x*b.y-a.y*b.x;
    }
    static bool isOrthogonal(Vector a,Vector b){
        return equals(dot(a,b),0.0);
    }
    static bool isOrthogonal(Point a1,Point a2,Point b1,Point b2){
        return isOrthogonal(a1-a2,b1-b2);
    }
    static bool isParallel(Vector a,Vector b){
        return equals(cross(a,b),0.0);
    }
    static bool isParallel(Point a1,Point a2,Point b1,Point b2){
        return isParallel(a1-a2,b1-b2);
    }
    static double abs(Point p){
        return sqrt(norm(p));
    }
    static double norm(Point p){
        return p.x*p.x+p.y*p.y;
    }
    static Point project(Segment s,Point p){//投影
        Vector base=s.p2-s.p1;
        double r=dot(p-s.p1,base)/norm(base);
        return s.p1+base*r;
    }
    static double getDistance(Point a,Point b){
        return abs(a-b);
    }
    static double getDistanceLP(Line l,Point p){
        return abs(cross(l.p2-l.p1,p-l.p1))/abs(l.p2-l.p1);
    }
    static double getDistanceSP(Segment s,Point p){
        if(dot(s.p2-s.p1,p-s.p1)<0) return abs(p-s.p1);
        if(dot(s.p1-s.p2,p-s.p2)<0) return abs(p-s.p2);
        return getDistanceLP(s,p);
    }
    static double getDistance(Segment s1,Segment s2){
        if(intersect(s1,s2)) return 0.0;
        return fmin(fmin(getDistanceSP(s1,s2.p1),getDistanceSP(s1,s2.p2)),
                    fmin(getDistanceSP(s2,s1.p1),getDistanceSP(s2,s1.p2)));
    }
    //p2在p0->p1的方位
    static int ccw(Point p0,Point p1,Point p2){
        //counter clockwise
        static const int COUNTER_CLOCKWISE =1;
        static const int CLOCKWISE =-1;
        static const int ONLINE_BACK =2;
        static const int ONLINE_FRONT =-2;
        static const int ON_SEGMENT =0;

        Vector a=p1-p0;
        Vector b=p2-p0;

        return ccw(a,b);
    }
    //b相对于a的方位
    static int ccw(Vector a,Vector b){
        //counter clockwise
        static const int COUNTER_CLOCKWISE =1;//逆时针
        static const int CLOCKWISE =-1;//顺时针
        static const int ONLINE_BACK =2;
        static const int ONLINE_FRONT =-2;
        static const int ON_SEGMENT =0;

        if(cross(a,b)>EPS)return COUNTER_CLOCKWISE;
        if(cross(a,b)<-EPS)return CLOCKWISE;
        if(dot(a,b)<-EPS)return ONLINE_BACK;
        if(a.norm()<b.norm())return ONLINE_FRONT;
        return ON_SEGMENT;
    }
    static bool intersect(Point p1,Point p2,Point p3,Point p4){//seg1: p1p2 seg2: p3p4
        return (ccw(p1,p2,p3)*ccw(p1,p2,p4)<0&&
                ccw(p3,p4,p1)*ccw(p3,p4,p2)<0);
    }
    static bool intersect(Segment s1,Segment s2){//seg1: p1p2 seg2: p3p4
        return intersect(s1.p1,s1.p2,s2.p1,s2.p2);
    }
    static Point getCrossPoint(Segment s1,Segment s2){
        Vector base = s2.p2-s2.p1;
        double d1=abs(cross(base,s1.p1-s2.p1));
        double d2=abs(cross(base,s1.p2-s2.p1));
        double t=d1/(d1+d2);
        return s1.p1+(s1.p2-s1.p1)*t;
    }
    static inline bool almostEqual(double num1,double num2){
        const double TOL=1e-5;
        if(fabs(num1-num2)<TOL){
            return true;
        }
        return false;
    }
    static bool onSegment(Point endPoint1,Point endPoint2,Point p){
        if(p==endPoint1||p==endPoint2){
            return false;
        }
        Segment segment=Segment(endPoint1,endPoint2);
        return equals(getDistanceSP(segment,p),0.0);
    }
    static bool onSegment(Point p,Segment s){
        return onSegment(s.p1,s.p2,p);
    }
    static double getSignedDistanceLP(Line l,Point p){
        ////求点P到直线AB的带符号距离（当P在AB左侧时距离为正，右侧时为负）
        Vector dir=l.p2-l.p1;
        Vector leftNormal=Vector(-dir.y,dir.x).normalize();
        Vector AP=p-l.p1;
        return dot(AP,leftNormal);
    }

    static double distanceOnDirPS(Segment s,Point p,Vector dir){
        //过p点，方向为dir的直线与线段s的交点，求交点与p之间的距离
        //点在线段上返回0，无交点返回-1，交点在线段的端点上，返回-1
        //https://www.cnblogs.com/wantnon/p/6384543.html
        Line dirLine=Line(p,p+dir);
        double d1=getSignedDistanceLP(dirLine,s.p1);
        double d2=getSignedDistanceLP(dirLine,s.p2);
        if(d1*d2<0&&!equals(d1*d2,0.0)){//交点存在且交点非线段的端点
            double D1=fabs(d1);
            double D2=fabs(d2);
            if(!equals(D1+D2,0.0)){
                double k=D1/(D1+D2);
                Point intersection=s.p1+(s.p2-s.p1)*k;
                if(ccw(p,p+dir,intersection)<=0){
                    return getDistance(intersection,p);
                } else{
                    return -1;
                }
            } else{
                return -1;
            }
        } else{
            return -1;
        }
    }
    //多边形相交检测，如果两多边形相离或仅在边上有接触，返回false
    static bool intersect(Polygon *A,Polygon *B){
        //准备使用点是否在多边形内+线是否相交+
        //如点在另一多边形边上，判断它旁边两条边与这条边的位置，如在两侧则相交
        if(!allOutside(A,B)||!allOutside(B,A)){
            return true;
        }
        Vector offseta=A->offset,offsetb=B->offset;
        for(int i=0;i<A->lenth;i++){
            Point pa=A->getPoint(i)+offseta;
            Point nextpa=((i==A->lenth-1)?A->getPoint(0):A->getPoint(i+1))+offseta;
            Segment sa=Segment(pa,nextpa);
            for(int j=0;j<B->lenth;j++){
                Point pb=B->getPoint(j)+offsetb;
                Point nextpb=((j==B->lenth-1)?B->getPoint(0):B->getPoint(j+1))+offsetb;
                Segment sb=Segment(pb,nextpb);
                if(intersect(sa,sb)){
                    return true;
                }
                if(onSegment(pa,sb)){
                    Point lastpa=((i==0)?A->getPoint(A->lenth-1):A->getPoint(i-1))+offseta;
                    Vector v=sb.p2-sb.p1;
                    if(ccw(v,lastpa-pa)*ccw(v,nextpa-pa)==-1){
                        return true;
                    }
                }
                if(onSegment(pb,sa)){
                    Point lastpb=((j==0)?B->getPoint(B->lenth-1):B->getPoint(j-1))+offsetb;
                    Vector v=sa.p2-sa.p1;
                    if(ccw(v,lastpb-pb)*ccw(v,nextpb-pb)==-1){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    static bool allInside(Polygon *inside,Polygon *outer){
        Vector insideOffset=inside->offset;
        for(int i=0;i<inside->lenth;i++){
            Point p=inside->getPoint(i)+insideOffset;
            bool pInside=pointInPolygon(p,outer);
            if(pInside== false){
                return false;
            }
        }
        return true;
    }
    static bool allOutside(Polygon *outside,Polygon *outer){
        Vector outsideOffset=outside->offset;
        int counter=0;
        for(int i=0;i<outside->lenth;i++){
            Point p=outside->getPoint(i)+outsideOffset;
            int pOutside=pointOutPolygon(p,outer);
            if(pOutside==-1){
                counter++;
            }
            if(pOutside== false){
                return false;
            }
        }
        if(counter==outside->lenth){
            return false;
        }
        return true;
    }
    static Polygon *copyPolygon(Polygon *p){
        Polygon *newp=new Polygon();
        for(int i=0;i<p->lenth;i++){
            newp->add(p->getPoint(i));
        }
        newp->offset=p->offset;
        return newp;
    }
    static Polygon *rotatePolygon(Polygon * polygon,double degree){
        //https://blog.csdn.net/TOM_00001/article/details/62054572
        Polygon *rotatedPolygon=new Polygon();
        if(equals(degree,0.0)){
            for(int i=0;i<polygon->lenth;i++){
                double x=polygon->getx(i),y=polygon->gety(i);
                rotatedPolygon->add(x,y);
            }
            return rotatedPolygon;
        }
        double radian=degree * M_PI /180.0;
        double sina=sin(radian), cosa=cos(radian);
        for(int i=0;i<polygon->lenth;i++){
            double x=polygon->getx(i),y=polygon->gety(i);
            double x1=x*cosa-y*sina;
            double y1=x*sina+y*cosa;
            rotatedPolygon->add(x1,y1);
        }
        return rotatedPolygon;
    }
    static double binWidth(NestPath bin){
        return 0;
    }
    //两多边形的每个点到另一个多边形的边的最短距离（转换到下一个接触的状态），用来寻找可能的滑动距离
    static double minPolygonDisOnDir(Polygon * fixed,Polygon * move,Vector dir){
        double minDirDistance=DBL_MAX;//记录大于0的最短距离
        Vector reverse=Vector(-dir.x,-dir.y);
        double lastDis=0;
        //先对于move的每一个点，看到另一个多边形（的点或边）的最短距离
        for(int i=0;i<move->lenth;i++){
            Point p=move->getPoint(i)+move->offset;
            for(int j=0;j<fixed->lenth;j++){
                int nextj=(j==fixed->lenth-1)?0:j+1;
                Point p1=fixed->getPoint(j);
                Segment s=Segment(p1+fixed->offset,fixed->getPoint(nextj)+fixed->offset);
                if(ccw(dir,p1-p)==-2||ccw(dir,p1-p)==0){
                    double d1=abs(p1-p);
                    if(!equals(d1,0)){
                        minDirDistance=d1<minDirDistance?d1:minDirDistance;
                    }
                }
                double d=distanceOnDirPS(s,p,dir);
                //找出最小的d
                if(d<0||equals(d,0)){
                    //点在线上或者无交点
                } else{
                    //find the min distance
                    minDirDistance=d<minDirDistance?d:minDirDistance;
                }
            }
        }
        //反过来
        for(int i=0;i<fixed->lenth;i++){
            Point p=fixed->getPoint(i)+fixed->offset;
            for(int j=0;j<move->lenth;j++){
                int nextj=(j==move->lenth-1)?0:j+1;
                Point p1=move->getPoint(j);
                Segment s=Segment(p1+move->offset,move->getPoint(nextj)+move->offset);
                if(ccw(reverse,p1-p)==-2||ccw(reverse,p1-p)==0){
                    double d1=abs(p1-p);
                    if(!equals(d1,0)){
                        minDirDistance=d1<minDirDistance?d1:minDirDistance;
                    }
                }
                double d=distanceOnDirPS(s,p,reverse);
                //找出最小的d
                if(d<0||equals(d,0)){
                    //点在线上或者无交点
                } else{
                    //find the min distance
                    minDirDistance=d<minDirDistance?d:minDirDistance;
                }
            }
        }
        return minDirDistance;
    }
    //如果不会相交返回-1,立刻相交返回0,正数为移动距离
    static double segmentDistanceOnDir(Point f1,Point f2,Point o1,Point o2,Vector dir){

        //需要考虑线的一点在另一线上的情况,进行直接判断
        //        if(intersect(f1,f2,o1,o2)){
        //            std::cout<<"instance return"<<std::endl;
        //            return 0;//立即相交
        //        }

        Vector normal=Vector(dir.y,-dir.x);

        Vector reverse=Vector(-dir.x,-dir.y);

        double dotNormf1=dot(f1,normal);
        double dotNormf2=dot(f2,normal);
        double dotNormo1=dot(o1,normal);
        double dotNormo2=dot(o2,normal);

        double dotDirf1=dot(f1,dir);
        double dotDirf2=dot(f2,dir);
        double dotDiro1=dot(o1,dir);
        double dotDiro2=dot(o2,dir);

        double maxNormf=fmax(dotNormf1,dotNormf2);
        double minNormf=fmin(dotNormf1,dotNormf2);

        double maxNormo=fmax(dotNormo1,dotNormo2);
        double minNormo=fmin(dotNormo1,dotNormo2);

        if(equals(maxNormf,minNormo)||equals(minNormf,maxNormo)){
            return -1;//不会相交
        }
        if(maxNormf<minNormo||minNormf>maxNormo){
            return -1;//不会相交
        }

        Vector f1f2=f2-f1;
        Vector f1o1=o1-f1;
        Vector f1o2=o2-f1;

        double crossf1f2o1=cross(f1f2,f1o1);
        double crossf1f2o2=cross(f1f2,f1o2);

        if(equals(crossf1f2o1,0.0)&&equals(crossf1f2o2,0.0)){
            // lines are colinear
            if(equals(maxNormf,maxNormo)&&equals(minNormf,minNormo)){
                if(equals(dot(f1f2,dir),0.0)){
                    return 0;
                }
                return -DBL_MAX;
            }
            return -1;
        }

        if(f1==o1){//在两条线有一个点重合时，判断移动是否会相交
            Vector o2o1=o1-o2;
            Vector f1f2=f2-f1;
            if(ccw(f1f2,o2o1)==1){
                if(ccw(f1f2,dir)==1&&ccw(o2o1,dir)==-1){
                    return 0;
                }
            } else if(ccw(f1f2,o2o1)==-1){
                if(ccw(f1f2,dir)==-1&&ccw(o2o1,dir)==1){
                    return 0;
                }
            }
            return -1;
        } else if(f1==o2){
            Vector o1o2=o2-o1;
            Vector f1f2=f2-f1;
            if(ccw(f1f2,o1o2)==1){
                if(ccw(f1f2,dir)==1&&ccw(o1o2,dir)==-1){
                    return 0;
                }
            } else if(ccw(f1f2,o1o2)==-1){
                if(ccw(f1f2,dir)==-1&&ccw(o1o2,dir)==1){
                    return 0;
                }
            }
            return -1;
        } else if(f2==o1){
            Vector o2o1=o1-o2;
            Vector f2f1=f1-f2;
            if(ccw(f2f1,o2o1)==1){
                if(ccw(f2f1,dir)==1&&ccw(o2o1,dir)==-1){
                    return 0;
                }
            } else if(ccw(f2f1,o2o1)==-1){
                if(ccw(f2f1,dir)==-1&&ccw(o2o1,dir)==1){
                    return 0;
                }
            }
            return -1;
        } else if(f2==o2){
            Vector o1o2=o2-o1;
            Vector f2f1=f1-f2;
            if(ccw(f2f1,o1o2)==1){
                if(ccw(f2f1,dir)==1&&ccw(o1o2,dir)==-1){
                    return 0;
                }
            } else if(ccw(f2f1,o1o2)==-1){
                if(ccw(f2f1,dir)==-1&&ccw(o1o2,dir)==1){
                    return 0;
                }
            }
            return -1;
        }

        if(onSegment(f1,f2,o1)){//点在线上的情况
            Vector o1o2=o2-o1;
            Vector f1f2=f2-f1;
            if(ccw(f1f2,dir)*ccw(f1f2,o1o2)==-1){
                return 0;
            }
            return -1;
        } else if(onSegment(f1,f2,o2)){
            Vector o2o1=o1-o2;
            Vector f1f2=f2-f1;
            if(ccw(f1f2,dir)*ccw(f1f2,o2o1)==-1){
                return 0;
            }
            return -1;
        } else if(onSegment(o1,o2,f1)){
            Vector o1o2=o2-o1;
            Vector f1f2=f2-f1;
            if(ccw(o1o2,dir)*ccw(o1o2,f1f2)==1){//同方向
                return 0;
            }
            return -1;
        } else if(onSegment(o1,o2,f2)){
            Vector o1o2=o2-o1;
            Vector f2f1=f1-f2;
            if(ccw(o1o2,dir)*ccw(o1o2,f2f1)==1){
                return 0;
            }
            return -1;
        }

        double distance=-1;

        if(equals(dotNormf1,dotNormo1)){
            double d=dotDirf1-dotDiro1;//如果为负，说明渐行渐远
            if(distance<0 && d>0){
                distance=d;
            }
            else if(d>0){
                distance=fmin(distance,d);
            }
        } else if(equals(dotNormf1,dotNormo2)){
            double d=dotDirf1-dotDiro2;
            if(distance<0 && d>0){
                distance=d;
            }
            else if(d>0){
                distance=fmin(distance,d);
            }
        } else if(dotNormf1>minNormo && dotNormf1<maxNormo){
            //f1在o1o2之间
            Segment s=Segment(o1,o2);
            double d=distanceOnDirPS(s,f1,reverse);
            if(distance<0 && d>0){
                distance=d;
            }
            else if(d>0){
                distance=fmin(distance,d);
            }
        }

        if(equals(dotNormf2,dotNormo1)){
            double d=dotDirf2-dotDiro1;
            if(distance<0 && d>0){
                distance=d;
            }
            else if(d>0){
                distance=fmin(distance,d);
            }
        } else if(equals(dotNormf2,dotNormo2)){
            double d=dotDirf2-dotDiro2;
            if(distance<0 && d>0){
                distance=d;
            }
            else if(d>0){
                distance=fmin(distance,d);
            }
        }else if(dotNormf2>minNormo && dotNormf2<maxNormo){
            //f2在o1o2之间
            Segment s=Segment(o1,o2);
            double d=distanceOnDirPS(s,f2,reverse);
            if(distance<0 && d>0){
                distance=d;
            }
            else if(d>0){
                distance=fmin(distance,d);
            }
        }

        if(dotNormo1>minNormf && dotNormo1<maxNormf){
            //o1在f1f2之间
            Segment s=Segment(f1,f2);
            double d=distanceOnDirPS(s,o1,dir);
            if(distance<0 && d>0){
                distance=d;
            }
            else if(d>0){
                distance=fmin(distance,d);
            }
        }

        if(dotNormo2>minNormf && dotNormo2<maxNormf){
            //o2在f1f2之间
            Segment s=Segment(f1,f2);
            double d=distanceOnDirPS(s,o2,dir);
            if(distance<0 && d>0){
                distance=d;
            }
            else if(d>0){
                distance=fmin(distance,d);
            }
        }

        return distance;
    }
    static double polygonSlideDistance(Polygon *fixed,Polygon *orbited,Vector direction){
        //-1为不会相交，0为立刻相交，正数为最短距离
        std::vector<Point> fixedPoints=fixed->pointVector;
        std::vector<Point> orbitedPoints=orbited->pointVector;
        fixedPoints.push_back(fixedPoints[0]);
        orbitedPoints.push_back(orbitedPoints[0]);

        //std::cout<<"Points size is "<<fixedPoints.size()<<std::endl;

        Vector fixedOffset=fixed->offset;
        Vector orbitedOffset=orbited->offset;

        Vector dir=direction.normalize();

        //std::cout<<"direction is ("<<dir.x<<","<<dir.y<<")"<<std::endl;

        double minDistance=-1;

        for(int i=0;i<fixedPoints.size()-1;i++){
            Point f1=fixedPoints[i]+fixedOffset;
            Point f2=fixedPoints[i+1]+fixedOffset;
            if(f1==f2){
                continue;// ignore extremely small lines
            }

            for(int j=0;j<orbitedPoints.size()-1;j++){
                Point o1=orbitedPoints[j]+orbitedOffset;
                Point o2=orbitedPoints[j+1]+orbitedOffset;
                if(o1==o2){
                    continue;// ignore extremely small lines
                }

                double d=segmentDistanceOnDir(f1,f2,o1,o2,dir);

                //                std::cout<<"line "<<i<<","<<j<<" d is "<<d<<std::endl;

                if(equals(d,-DBL_MAX)){
                    orbited->offset=orbited->offset+(dir*0.01);
                    if(intersect(fixed,orbited)){
                        d=0;
                    }
                    orbited->offset=orbited->offset-(dir*0.01);
                }
                if(equals(d,0.0)){
                    return 0;//有一条线相交，即直接判断移动距离为0
                }

                if(d>0 && minDistance<0){
                    minDistance=d;
                }
                if(d>0&&d<minDistance){
                    minDistance=d;
                }
            }
        }
        return minDistance;
    }
    static int dcmp(double x)
    {
        if(fabs(x)<EPS) return 0;
        else
            return x<0?-1:1;
    }
    static bool pointInPolygon(Point p,Polygon *polygon){
        //点在多边形上或多边形内部都返回true
        //https://blog.csdn.net/WilliamSun0122/article/details/77994526
        bool flag = false; //相当于计数
        Point P1,P2; //多边形一条边的两个顶点
        Vector offset=polygon->offset;
        for(int i=0,j=polygon->lenth-1;i<polygon->lenth;j=i++)
        {
            //多边形的顶点
            P1 = polygon->getPoint(i)+offset;
            P2 = polygon->getPoint(j)+offset;
            if(P1==p||P2==p) return true;//点在顶点上
            if(onSegment(P1,P2,p)) return true; //点在多边形一条边上
            //前一个判断min(P1.y,P2.y)<P.y<=max(P1.y,P2.y)
            //这个判断代码我觉得写的很精妙 我网上看的 应该是大神模版
            //后一个判断被测点 在 射线与边交点 的左边
            if( (dcmp(P1.y-p.y)>0 != dcmp(P2.y-p.y)>0) && dcmp(p.x - (p.y-P1.y)*(P1.x-P2.x)/(P1.y-P2.y)-P1.x)<0){
                flag = !flag;
            }
        }
        return flag;
    }
    static int pointOutPolygon(Point p,Polygon *polygon){
        //点在多边形上或多边形外部都返回true,在多边形上返回-1,外部返回1,内部返回0
        //https://blog.csdn.net/WilliamSun0122/article/details/77994526
        bool flag = true; //相当于计数
        Point P1,P2; //多边形一条边的两个顶点
        Vector offset=polygon->offset;
        for(int i=0,j=polygon->lenth-1;i<polygon->lenth;j=i++)
        {
            //多边形的顶点
            P1 = polygon->getPoint(i)+offset;
            P2 = polygon->getPoint(j)+offset;
            if(P1==p||P2==p) return -1;//点在顶点上
            if(onSegment(P1,P2,p)) return -1; //点在多边形一条边上
            //前一个判断min(P1.y,P2.y)<P.y<=max(P1.y,P2.y)
            //这个判断代码我觉得写的很精妙 我网上看的 应该是大神模版
            //后一个判断被测点 在 射线与边交点 的左边
            if( (dcmp(P1.y-p.y)>0 != dcmp(P2.y-p.y)>0) && dcmp(p.x - (p.y-P1.y)*(P1.x-P2.x)/(P1.y-P2.y)-P1.x)<0){
                flag = !flag;
            }
        }
        return flag;
    }
    static double polygonDirDistance(Polygon *fixed,Polygon* move,Vector dir){
        /*
         *作用应该仅仅为让两个多边形紧贴/相交（修改为让两个多边形内接可好？）
         */
        Vector reverse=Vector(-dir.x,-dir.y);
        double distance=-DBL_MAX;
        for(int i=0;i<move->lenth;i++){
            double minDirDistance=DBL_MAX;
            for(int j=0;j<fixed->lenth;j++){
                Point p=move->offset+move->getPoint(i);
                int nextj=(j==fixed->lenth-1)?0:j+1;
                Segment s=Segment(fixed->getPoint(j)+fixed->offset,fixed->getPoint(nextj)+fixed->offset);
                if(fabs(cross(dir,s.p2-s.p1))<EPS){
                    continue;
                }
                double d1=distanceOnDirPS(s,p,dir);
                double d2=distanceOnDirPS(s,p,reverse);
                //找出最小的d
                if(d1<0&&d2<0){
                    //distance is inf
                } else{
                    //find the min distance/biggest negative distance
                    if(d2>0||equals(d2,0)){
                        minDirDistance=minDirDistance<(-d2)?minDirDistance:(-d2);
                    } else if(d1>0||equals(d1,0)){
                        minDirDistance=minDirDistance<d1?minDirDistance:d1;
                    }
                }
            }
            if(!equals(minDirDistance,DBL_MAX)){
                distance=minDirDistance>distance?minDirDistance:distance;//find the max
            }
        }
        return distance;
    }
    //通过论文中的方法，寻找下一个起始点
    static bool findNextStartPoint(Polygon *fixed,Polygon *orbited,Vector &returnVector){
        orbited=copyPolygon(orbited);
        Vector orbitedOffset=orbited->offset;
        for(int i=0;i<fixed->lenth&&fixed->isMarked(i)== false;i++){
            fixed->mark(i);
            Point f1=fixed->getPoint(i);
            int nextiIndex=(i==fixed->lenth-1)?0:i+1;
            Point f2=fixed->getPoint(nextiIndex);
            //给予A的一条边e,沿着e检测潜在的起始点
            for(int j=0;j<orbited->lenth;j++){
                //平移B,使B每个顶点,以此说e的起始顶点对齐
                Vector shiftVector=f1-(orbited->getPoint(j)+orbitedOffset);//B的顶点
                orbited->offset=orbitedOffset+shiftVector;
                if(allOutside(orbited,fixed)&&!intersect(fixed,orbited)){//移动后不仅有一点紧贴，所有点都在内部
                    delete orbited;
                    returnVector=shiftVector;
                    return true;
                } else{
                    //检测与A顶点相交的两条边
                    int lastjIndex=(j==0)?(orbited->lenth-1):j-1;
                    int nextjIndex=(j==orbited->lenth-1)?0:j+1;
                    Point o1=orbited->getPoint(lastjIndex);
                    Point o2=orbited->getPoint(j);//o2为相交的点
                    Point o3=orbited->getPoint(nextjIndex);
                    Vector e1=o1-o2;
                    Vector e2=o3-o2;
                    Vector e=f2-f1;
                    if(ccw(e,e1)!=1&&ccw(e,e2)!=1){
                        double maxSlideDistance=abs(e);
                        double totalSlideDistance=0;
                        while (totalSlideDistance<maxSlideDistance){
                            double slideDistance=minPolygonDisOnDir(fixed,orbited,e);
                            if(slideDistance==DBL_MAX){
                                break;
                            }
                            totalSlideDistance+=slideDistance;
                            Vector offsetOrbited=orbited->offset+(e/abs(e)*slideDistance);
                            shiftVector=shiftVector+(e/abs(e)*slideDistance);
                            orbited->offset=offsetOrbited;
                            if(allOutside(orbited,fixed)&&!intersect(fixed,orbited)){
                                delete orbited;
                                returnVector=shiftVector;
                                return true;
                            }
                        }
                    } else{
                        continue;
                    }
                }
            }
        }
        delete orbited;
        return false;
    }
    //通过平移向量来找到起始点,fix为底板，orbited为摆件
    static bool searchIfpShift(Polygon *fixed ,Polygon *orbited,Vector &returnVector){
        orbited=copyPolygon(orbited);
        Vector orbitedOffset=orbited->offset;
        for(int i=0;i<fixed->lenth;i++){
            Point f1=fixed->getPoint(i);
            int nextiIndex=(i==fixed->lenth-1)?0:i+1;
            Point f2=fixed->getPoint(nextiIndex);
            //给予A的一条边e,沿着e检测潜在的起始点
            for(int j=0;j<orbited->lenth;j++){
                //平移B,使B每个顶点,以此说e的起始顶点对齐
                Vector shiftVector=f1-(orbited->getPoint(j)+orbitedOffset);//B的顶点
                orbited->offset=orbitedOffset+shiftVector;
                if(allInside(orbited,fixed)){//移动后不仅有一点紧贴，所有点都在内部
                    delete orbited;
                    returnVector=shiftVector;
                    return true;
                } else{
                    //检测与A顶点相交的两条边
                    int lastjIndex=(j==0)?(orbited->lenth-1):j-1;
                    int nextjIndex=(j==orbited->lenth-1)?0:j+1;
                    Point o1=orbited->getPoint(lastjIndex);
                    Point o2=orbited->getPoint(j);//o2为相交的点
                    Point o3=orbited->getPoint(nextjIndex);
                    Vector e1=o1-o2;
                    Vector e2=o3-o2;
                    Vector e=f2-f1;
                    if(ccw(e,e1)!=1&&ccw(e,e2)!=1){
                        double maxSlideDistance=abs(e);
                        double totalSlideDistance=0;
                        while (totalSlideDistance<maxSlideDistance){
                            double slideDistance=minPolygonDisOnDir(fixed,orbited,e);
                            if(slideDistance==DBL_MAX){
                                break;
                            }
                            totalSlideDistance+=slideDistance;
                            Vector offsetOrbited=orbited->offset+(e/abs(e)*slideDistance);
                            shiftVector=shiftVector+(e/abs(e)*slideDistance);
                            orbited->offset=offsetOrbited;
                            if(allInside(orbited,fixed)){
                                delete orbited;
                                returnVector=shiftVector;
                                return true;
                            }
                        }
                    } else{
                        continue;
                    }
                }
            }
        }
        delete orbited;
        return false;
    }
    /*
     * 通过环绕的方式来求解两平面图形的外接多边形，inside为true则求解内接多边形
     * */
    static NestPath noFitPolygon(Polygon *fixed, Polygon *orbited, bool inside) {
        fixed=copyPolygon(fixed);
        orbited=copyPolygon(orbited);
        if(!fixed||fixed->lenth<3||!orbited||orbited->lenth<3){
            delete fixed;
            delete orbited;
            return NestPath();
        }

        fixed->offset=Vector();
        orbited->offset=Vector();

        Vector shiftVector;

        if(!inside){
            double minFixedY=fixed->pointVector[0].y;//固定图形的最低点
            int minFixedYIndex=0;
            for(int i=0;i<fixed->lenth;i++){
                if(fixed->pointVector[i].y<minFixedY){
                    minFixedY=fixed->pointVector[i].y;
                    minFixedYIndex=i;
                }
            }

            double maxOrbitedY=orbited->pointVector[0].y;//环绕图形的最高点
            int maxOrbitedYIndex=0;
            for(int i=0;i<orbited->lenth;i++){
                if(orbited->pointVector[i].y>maxOrbitedY){
                    maxOrbitedY=orbited->pointVector[i].y;
                    maxOrbitedYIndex=i;
                }
            }
            //计算偏移向量，使环绕图形紧贴固定图形，由最高点指向最低点，同时也是B的偏移量
            //        double shiftX=fixed->pointVector[minFixedYIndex].x-orbited->pointVector[maxOrbitedYIndex].x;
            //        double shiftY=fixed->pointVector[minFixedYIndex].y-orbited->pointVector[maxOrbitedYIndex].y;
            shiftVector=fixed->getPoint(minFixedYIndex)-orbited->getPoint(maxOrbitedYIndex);
        } else if(inside){
            //找出的可以使两图形紧贴的偏移
            if(searchIfpShift(fixed,orbited,shiftVector)){

            } else{
                std::cout<<"error in ifp"<<std::endl;
                delete fixed;
                delete orbited;
                return NestPath();
            }
        }

        //std::cout<<"shiftVector: ("<<shiftVector.x<<","<<shiftVector.y<<")"<<std::endl;

        std::vector<Polygon *> nfpList=std::vector<Polygon *>();

        bool searchEnd= false;
        while (!searchEnd){
            //参考点为orbited[0]
            Point referencePoint=shiftVector+orbited->getPoint(0);
            Point stratPoint=referencePoint;

            orbited->offset=shiftVector;

            Vector prevVector=Vector();

            Polygon *nfp=new Polygon();

            nfp->add(referencePoint);
            //            std::cout<<"referencePoint: ("<<referencePoint.x<<","<<referencePoint.y<<")"<<std::endl;

            int counter=0;
            while(counter < 10*(fixed->lenth + orbited->lenth)){

                std::vector<Vector> shiftVectors =std::vector<Vector>();

                //找到相邻的边对
                for(int i=0;i<fixed->lenth;i++){
                    int nexti= (i==fixed->lenth-1)?0:i+1;
                    int previ=(i==0)?fixed->lenth-1:i-1;

                    for(int j=0;j<orbited->lenth;j++){
                        int nextj=(j==orbited->lenth-1)?0:j+1;
                        int prevj=(j==0)?orbited->lenth-1:j-1;

                        Point *prevFixedPoint=&fixed->pointVector[previ];
                        Point *fixedPoint=&fixed->pointVector[i];
                        Point *nextFixedPoint=&fixed->pointVector[nexti];

                        Point *prevOrbitedPoint=&orbited->pointVector[prevj];
                        Point *orbitedPoint=&orbited->pointVector[j];
                        Point *nextOrbitedPoint=&orbited->pointVector[nextj];

                        //两点接触
                        if(*fixedPoint==(*orbitedPoint+shiftVector)){
                            fixedPoint->markPoint();
                            Vector v1=*prevFixedPoint-*fixedPoint;
                            v1.begin=fixedPoint;
                            v1.end=prevFixedPoint;
                            Vector v2=*nextFixedPoint-*fixedPoint;
                            v2.begin=fixedPoint;
                            v2.end=nextFixedPoint;
                            Vector v3=*orbitedPoint-*prevOrbitedPoint;
                            v3.begin=prevOrbitedPoint;
                            v3.end=orbitedPoint;
                            Vector v4=*orbitedPoint-*nextOrbitedPoint;
                            v4.begin=nextOrbitedPoint;
                            v4.end=orbitedPoint;

                            shiftVectors.push_back(v1);
                            shiftVectors.push_back(v2);
                            shiftVectors.push_back(v3);
                            shiftVectors.push_back(v4);
                            //点在边上
                        }else if(onSegment(*fixedPoint,*nextFixedPoint,*orbitedPoint+shiftVector)){
                            nextFixedPoint->markPoint();
                            Vector v1=*nextFixedPoint-(*orbitedPoint+shiftVector);
                            v1.begin=fixedPoint;
                            v1.end=nextFixedPoint;
                            Vector v2=*fixedPoint-(*orbitedPoint+shiftVector);
                            v2.begin=nextFixedPoint;
                            v2.end=fixedPoint;

                            shiftVectors.push_back(v1);
                            shiftVectors.push_back(v2);
                        }else if(onSegment(*orbitedPoint+shiftVector,*nextOrbitedPoint+shiftVector,*fixedPoint)){
                            fixedPoint->markPoint();
                            Vector v1=*fixedPoint-(*nextOrbitedPoint+shiftVector);
                            v1.begin=orbitedPoint;
                            v1.end=nextOrbitedPoint;
                            Vector v2=*fixedPoint-(*orbitedPoint+shiftVector);
                            v2.begin=nextOrbitedPoint;
                            v2.end=orbitedPoint;

                            shiftVectors.push_back(v1);
                            shiftVectors.push_back(v2);
                        }
                    }
                }

                std::set<Vector> shiftSet=std::set<Vector>(shiftVectors.begin(),shiftVectors.end());

                double maxd=0;
                Vector translateVector=Vector();
                //                std::cout<<"shiftVector size is "<<shiftVectors.size()<<std::endl;
                //                std::cout<<"shiftSet size is "<<shiftSet.size()<<std::endl;

                for(std::set<Vector>::iterator i=shiftSet.begin();i!=shiftSet.end();i++){
                    Vector vector=*i;
                    if(equals(vector.x,0.0)&&equals(vector.y,0.0)){
                        continue;
                    }
                    if(prevVector!=Vector()){//来路
                        if(dot(prevVector,vector)<0 && equals(cross(prevVector,vector),0.0)){
                            continue;
                        }
                    }

                    double d=polygonSlideDistance(fixed,orbited,vector);

                    //std::cout<<"shiftVector ("<<vector.x<<","<<vector.y<<") `s d is "<<d<<std::endl;

                    double norm=vector.norm();

                    //std::cout<<"norm ("<<vector.x<<","<<vector.y<<") is "<<norm<<std::endl;

                    if(d<0 || d*d>norm){//对比长度，长度不能大于向量原本的长度
                        d=sqrt(norm);
                    } else if(equals(d,0.0)){
                        //这条向量不行，会引起立即相交
                        continue;
                    }
                    if(d>maxd){//找一条最长的移动向量
                        maxd=d;
                        translateVector=vector;
                    }
                }

                if(equals(translateVector.x,0.0)&&equals(translateVector.y,0.0)){
                    Polygon *nfp=new Polygon();//运行错误
                    std::cout<<"error";
                    break;
                }

                //                std::cout<<"translateVector is ("<<translateVector.x<<","<<translateVector.y<<")"<<std::endl;

                //                std::cout<<"maxd is "<<maxd<<std::endl;

                if(translateVector.begin!= nullptr){
                    translateVector.begin->markPoint();
                }
                if(translateVector.end!= nullptr){
                    translateVector.end->markPoint();
                }

                translateVector=translateVector.normalize();
                prevVector=translateVector;
                translateVector=translateVector*maxd;
                referencePoint=referencePoint+translateVector;
                shiftVector=shiftVector+translateVector;

                //std::cout<<"referencePoint is ("<<referencePoint.x<<","<<referencePoint.y<<")"<<std::endl;

                if(referencePoint==stratPoint){//nfp构建完成
                    break;
                }
                nfp->add(referencePoint);
                //                std::cout<<"add Point ("<<referencePoint.x<<","<<referencePoint.y<<")"<<std::endl;

                orbited->offset=orbited->offset+translateVector;

                counter++;
            }

            if(nfp->lenth>0){
                nfpList.push_back(nfp);
            }
            Vector nextShift;
            bool notEnd=findNextStartPoint(fixed,orbited,nextShift);
            if(!notEnd){
                searchEnd= true;
            } else{
                orbited->offset=orbited->offset+nextShift;
            }
        }
        delete fixed;
        delete orbited;
        NestPath nestPath=NestPath(nfpList,-1,0);
        return nestPath;
    }

    // 获取包围该nestpath的boundingbox的宽和高
    static std::vector<double> getBoundingBoxSize(const NestPath& path){
        // path[0]即最外围路径
        double xmin = path[0]->getx(0);
        double xmax = path[0]->getx(0);
        double ymin = path[0]->gety(0);
        double ymax = path[0]->gety(0);

        for (int i = 1; i < path[0]->pointVector.size(); ++i) {
            double x = path[0]->getx(i);
            double y = path[0]->gety(i);
            if (x > xmax) {
                xmax = x;
            } else if (x < xmin) {
                xmin = x;
            }

            if (y > ymax) {
                ymax = y;
            } else if (y < ymin) {
                ymin = y;
            }
        }
        return {xmax - xmin, ymax - ymin}; //w, h
    }
};

#endif //BIN_PACKING_GEOMETRYUTILS_H

